
/*
 * Problems No 150
Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:
  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
  
 * 
 * 思路：
 * 比较简单了。重构二叉树就行了。从右向左处理。
 * 可以用递归实现。
 */
package com.leetcode.weicl.problems.no150;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;

/**
 * The Class Solution.<br>
 * 
 * @author FNST)WeiCL
 * @version 1.0
 */
public class Solution {
	int now = 0;
	
	public int evalRPN2(String[] tokens) {
		String last = tokens[now--];
		char opc = last.charAt(last.length()-1);
		if (opc >= '0' && opc <= '9' ) {
			return Integer.parseInt(last);
		} else {
			// 该节点为符号
			int right = evalRPN2(tokens);
			
			int left = evalRPN2(tokens);
			
			int ans = 0;
			
			if (opc == '+') {
				ans = left + right;
			} else if (opc == '-') {
				ans = left - right;
			} else if (opc == '*') {
				ans = left * right;
			} else if (opc == '/') {
				ans = left / right;
			}

//			System.out.println(ans);
			return ans;
		}
	}
	
	public int evalRPN(String[] tokens) {
//		LinkedList<String> list = new LinkedList<String>();
//		for (String s : tokens) {
//	        list.add(s);
//        }
		now = tokens.length - 1;
		return evalRPN2(tokens);
    }
	
	
	
	public static void main(String[] args) throws IOException {
	    Solution s = new Solution();
	    File f = new File("src/com/leetcode/weicl/problems/no150/large.file");
	    FileReader fr = new FileReader(f);
	    BufferedReader br = new BufferedReader(fr);
	    String str = br.readLine();
	    String[] ls = str.split("\",\"");
	    long start = System.currentTimeMillis();
	    System.out.println(s.evalRPN(ls));
	    System.out.println("time: " + (System.currentTimeMillis()- start) + " ms");
	    br.close();
	    
	    ls = new String[]{"3","-4","+"};
	    start = System.currentTimeMillis();
	    System.out.println(s.evalRPN(ls));
	    System.out.println("time: " + (System.currentTimeMillis()- start) + " ms");
    }
}
